7.5 KB · ⇊ 3 parts · ⤓ Micron 7.5 KB · ⤓ HTML 18.9 KB

top

La mwbaTuring equivalenza è la proprietà dei modelli di calcolo che hanno lo stesso mwbgpotere computazionale di una mwbwmacchina di Turing universale (mwcaMdTu).

Un modello che ha lo stesso potere computazionale di una MdTu si dice mwcgTuring equivalente o mwcwTuring completo.

• Noti modelli Turing equivalenti

• Curiosità

• Note

• Voci correlate

• Collegamenti esterni

I più noti modelli di calcolo Turing equivalenti sono:

• le mwegfunzioni ricorsive;

• il modello di Kleene basato sulle equazioni funzionali;

• il mwfqlambda calcolo di Church;

• la mwfwlogica combinatoria;

• gli mwgqalgoritmi normali di Markov;

• i sistemi combinatori di Post;

• le mwhqmacchine a registri elementari come la mwhgmacchina URM;

• il mwiacalcolo dei predicati (si veda in proposito il mwiqteorema di completezza di Gödel e il mwigteorema di Church).

Anche i più comuni mwjalinguaggi di programmazione, sia mwjqimperativi sia mwjgfunzionali, sono Turing equivalenti.

Poiché la compilazione di un programma richiede l'uso di costrutti condizionali, cicli e memoria illimitati, un linguaggio mwkageneral purpose dotato di tali costrutti (e quindi Turing equivalente) permette di scrivere un mwkqcompilatore. Ciò ha generato la consuetudine di considerare un generico linguaggio mwkg L {\displaystyle L} come Turing equivalente quando è possibile scrivere un compilatore di programmi mwkw L {\displaystyle L} usando mwla L {\displaystyle L} stesso. In realtà non è necessario attendere che un linguaggio venga usato in un simile progetto: è sufficiente che esibisca alcune proprietà elementari, come si vede dai modelli Turing equivalenti più semplici (ad esempio le macchine a registri elementari).

Esempi di modelli di calcolo che sono meno potenti di una MdT Universale sono le mwlgespressioni regolari, gli mwlwautomi a stati finiti e le mwmamacchine che terminano sempre.

• Il mwnaGioco della vita è considerato Turing equivalente.cite-ref-1[1]cite-ref-2[2]

• Nel mwpgvideogioco mwpwFactorio è possibile riprodurre il mwqaGioco della vita, pertanto anch'esso è considerato Turing equivalente.cite-ref-factorio1-3-0[3]cite-ref-factorio2-4-0[4]cite-ref-factorio3-5-0[5]

• Nel 2022 sul canale YouTube di mwtgsammyuri è stato caricato un video in cui giocando a mwtwMinecraft è riuscito a creare un computer per giocare mwuaMinecraft, pertanto anche questo è considerato Turing equivalente.

cite-note-11. ↑ mwvw(mwwamwwqEN) mwwgmwwwThis is a Turing Machine implemented in Conway's Game of Life, su mwxarendell-attic.org, 2 aprile 2005. mwxqURL consultato l'11 dicembre 2018 mwxg(archiviato dall'mwxwurl originale l'8 luglio 2009).

cite-note-22. ↑ mwyw(mwzamwzqEN) Calcyman, mwzgmwzwSpartan universal computer-constructor, su mwaaconwaylife.com, 16 giugno 2009. mwaqURL consultato l'11 dicembre 2018.

cite-note-factorio1-33. ↑ mwbq(mwbgmwbwEN) DaveMcW, mwcamwcqCombinator Game of Life, su mwcgfactorio.com, 24 luglio 2015. mwcwURL consultato l'11 dicembre 2018.

cite-note-factorio2-44. ↑ mwdwmweamweq (mwewmwfaEN) Aroma1997, mwfqmwfgConway's Game of Life in Factorio, su mwfwmwgaYouTube, 5 settembre 2017. mwgqURL consultato l'11 dicembre 2018.

cite-note-factorio3-55. ↑ mwhqmwhgmwhw (mwiqmwigEN) Aroma1997, mwiwmwjaConway's Game of Life in Factorio - How it works, su mwjqmwjgYouTube, 6 settembre 2017. mwjwURL consultato l'11 dicembre 2018.

• mwkwTesi di Church-Turing

• citerefmathworld(EN) Eric W. Weisstein, Universality, su MathWorld, Wolfram Research.